package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode0312 
* @author      : ganwei 
* @date        : 2020年5月16日 
* @Description : leetcode 312 戳气球 
*/
public class Leetcode0312 {
    /**
     * -解题思路，动态规划
     */
	public int maxCoins(int[] nums) {
    	int length = nums.length;
		int[] points = new int[length+2];
		points[0] = 1;
		points[length+1] = 1;
		for(int i = 1; i <= length; i++) {
			points[i] = nums[i-1];
		}
		
		int[][] dp = new int[length+2][length+2];
		for(int i=length; i >= 0; i--) {
			for(int j=i+1; j < length+2; j++) {
				for(int k = i+1; k <j; k++) {
					dp[i][j] = Math.max(dp[i][j], dp[i][k]+dp[k][j]+points[i]*points[j]*points[k]);
				}
			}
		}
		
    	return dp[0][length+1];
    }
	
	/**
	 * -解题思路，回溯，太过暴力，无法通过所有案例
	 */
	public int maxCoins_1(int[] nums) {
		
		return 0;
	}
    /**
     * -main
     */
    public static void main(String[] args) {
    	Leetcode0312 l0312 = new Leetcode0312();
    	int[] nums = {3,1,5,8};
    	System.out.println(l0312.maxCoins(nums));
    }
}
